package com.hardy.leetcode;

import java.util.ArrayList;

/**
 * 从字符串中找出合法的IP地址
 * User: Ruijie Date: 2016/9/8
 */
public class RestoreIpAddresses {

    public static ArrayList<String> restoreIpAddresses(String s) {
        ArrayList<String> res = new ArrayList<String>();
        if (s.length() > 12) {
            return res;
        }
        _restoreIpAddress(s, 0, "", res);
        ArrayList<String> result=new ArrayList<String>();
        for (String s1 : res) {
            int len = s1.split("\\.").length;
            if (len == 4) {
                result.add(s1);
            }
        }
        return result;
    }

    private static void _restoreIpAddress(String s, int start, String item, ArrayList<String> res) {
        if (start >= s.length()) {
            res.add(item);
            return;
        }
        for (int i = start; i < s.length(); i++) {
            String str = s.substring(start, i + 1);
            if (isLegal(str)) {
                String newStr;
                if (item.length() > 0) {
                    newStr = item + "." + str;
                } else {
                    newStr = str;
                }
                _restoreIpAddress(s, i + 1, newStr, res);
            }
        }
    }

    private static boolean isLegal(String str) {
        if (str.length() > 3) {
            return false;
        }
        if(str.length()==3&&str.charAt(0)=='0'){
            return false;
        }
        if(str.length()==2&&str.charAt(0)=='0'){
            return false;
        }
        Integer num = Integer.parseInt(str);
        if (num <= 255 && num >= 0) {
            return true;
        }
        return false;
    }

    public static void main(String[] args) {
        String s = "010010";
        System.out.println(restoreIpAddresses(s));

    }

}
